#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include "strmap.h"

#define NTHREADS 4

//Wrapper para alocação de memória. Termina o programa e
//exibe mensagem de erro caso a alocação não tenha sido feita com sucesso.
void* allocate(int bytes);

//Verifica se a palavra é palíndromo.
int palindromo(char* palavra);

//Retorna a soma dos códigos ASCII de cada letra da palavra.
int word_to_ascii(char* palavra);

//Algoritmo do crivo de Erastótenes. Modificado para execução paralela.
void erastotenes(int** primos, int max_primo, int rank, int nodes);

//Busca binária (utilizada na verificação de se um número é primo)
int busca_binaria(int* vetor, int tamanho, int chave);

//Somente os seguintes caracteres são considerados
//como separadores, respectivamente: todos, de frase e de palavra.
//Sendo assim, frases são consideradas todo conjunto de caracteres
//separado por algum dos caracteres em SEPARADORES_FRASE. Palavras
//são consideradas todo conjunto de caracteres separado por algum dos
//caracteres em SEPARADORES.
char SEPARADORES[]         = " \n\r\t.,:;\"!?-()'";
char SEPARADORES_FRASE[]   = "\n\r\t.!?";
char SEPARADORES_PALAVRA[] = " ,:;\"-()'";

int main(int argc, char* argv[])
{
   struct timeval ti, tf;
   long int sec, usec;
   
   //Início da contagem de tempo
   gettimeofday(&ti, NULL);


   int mode; //Modo de execução (1 - menor texto, 2 - maior texto)
   int id, nodes;
   int *chunk_ind, diff;
   int file_size;
   int i, j, num_palavras, num_palindromos, num_palindromos_thread, num_frases, max_ascii, num_primos;
   int *primos, *crivo;
   int* soma_ascii;
   char *text, *text_buffer, *aux, *aux2;
   char buffer[2046];
   char **palavras, **frases;
   FILE *fp;
   StrMap *sm;
   
   mode = atoi(argv[1]);
   nodes = NTHREADS;
   
   omp_set_num_threads(NTHREADS);
   
   //Determina o tamanho do arquivo
   fp = fopen(argv[2], "rb");
   fseek(fp, 0L, SEEK_END);
   file_size = ftell(fp);
   rewind(fp);

   //Lê o texto em memória como uma única string
   text_buffer = (char*) allocate((file_size + 1) * sizeof(char));
   if(fread(text_buffer, 1, file_size, fp) != file_size)
   {
      printf("Erro na leitura do arquivo.\n");
      exit(0);
   }
   text_buffer[file_size] = '\0';
   
   //Converte o texto para lowercase
   for(i = 0; i < file_size; i++)
      text_buffer[i] = tolower(text_buffer[i]);

   //Determina os tamanhos dos buffers em cada nó escravo
   chunk_ind = (int*) allocate(nodes * sizeof(int));
   for(i = 0; i < nodes; i++)
      chunk_ind[i] = i * (file_size / nodes);
         
   //Correção para frases que não terminam exatamente na fronteira entre
   //a região de processamento de nós consecutivos. Aumenta o buffer do
   //anterior e diminui o do seguinte para corrigir.
   for(i = 1; i < nodes; i++)
   {
      diff = strlen(strtok(&text_buffer[chunk_ind[i]], SEPARADORES_FRASE)) + 1;
      chunk_ind[i] += diff;
   }

   //Copia o buffer para um outro (que será modificado no processo)
   text = (char*) allocate((file_size + 1) * sizeof(char));
   memcpy(text, text_buffer, file_size + 1);


   palavras = (char**) allocate(file_size * sizeof(char*));
      
   sm = sm_new(file_size);
   max_ascii = 0;
   num_palindromos = 0;
   printf("Palindromos:\n\n");
   
   //Inicia seção paralela do código
   #pragma omp parallel private(i, j, id, aux, aux2, buffer, num_palavras, num_frases, soma_ascii, num_palindromos_thread) shared(sm, max_ascii, num_palindromos, crivo, primos, num_primos)
   {
      id = omp_get_thread_num();
      
      //Grava posições das palavras
      palavras[chunk_ind[id]] = strtok_r(&text[chunk_ind[id]], SEPARADORES, &aux);
      for(num_palavras = 0; palavras[chunk_ind[id] + num_palavras] != NULL; )
         palavras[chunk_ind[id] + ++num_palavras] = strtok_r(NULL, SEPARADORES, &aux);
      
      #pragma omp barrier
      if(mode == 2)
         soma_ascii = (int*) allocate(num_palavras * sizeof(int));
      
      //Identifica palíndromos
      for(i = 0, num_palindromos_thread = 0; i < num_palavras; i++)
      {
         if(palindromo(palavras[chunk_ind[id] + i]))
         {
            #pragma omp critical
            if(!sm_exists(sm, palavras[chunk_ind[id] + i]))
            {
               sm_put(sm, palavras[chunk_ind[id] + i], "");
               j = 1;
            }
            else
               j = 0;
              
            if(j)
            {             
               if(mode == 2)
               {
                  soma_ascii[num_palindromos_thread] = word_to_ascii(palavras[chunk_ind[id] + i]);
                  if(max_ascii < soma_ascii[num_palindromos_thread])
                     max_ascii = soma_ascii[num_palindromos_thread];               
                  printf("(%d, %d): %s\n", id, ++num_palindromos_thread, palavras[chunk_ind[id] + i]);
               }
               else
                  printf("%d: %s\n", ++num_palindromos, palavras[chunk_ind[id] + i]);
            } 
         }
      }
      
      //Repete o mesmo processo, porém com frases
      if(mode == 1)
      {
         strcpy(&text[chunk_ind[id]], &text_buffer[chunk_ind[id]]);  
         frases = palavras;

         frases[chunk_ind[id]] = strtok_r(&text[chunk_ind[id]], SEPARADORES_FRASE, &aux);
         for(num_frases = 0; frases[chunk_ind[id] + num_frases] != NULL; )
            frases[chunk_ind[id] + ++num_frases] = strtok_r(NULL, SEPARADORES_FRASE, &aux);
         for(i = 0; i < num_frases; i++)
         {
            aux2 = strtok_r(frases[chunk_ind[id] + i], SEPARADORES_PALAVRA, &aux);
            buffer[0] = '\0';
            while(aux2 != NULL)
            {
               strcat(buffer, aux2);
               aux2 = strtok_r(NULL, SEPARADORES_PALAVRA, &aux);
            }
               
            if(palindromo(buffer))
            {
               #pragma omp critical
               if(!sm_exists(sm, buffer))
               {
                  sm_put(sm, buffer, "");
                  j = 1;
               }
               else
                  j = 0;
                  
               if(j)
               {
                  sm_put(sm, buffer, "");
                  printf("%d: %s\n", ++num_palindromos, buffer);
               }
            }
         }
      }
      
      //Encontra números primos nas somas ASCII
      if(mode == 2)
      {
         #pragma omp barrier
         if(id == 0)
         {
            printf("\nSomas ASCII primas:\n\n");
            crivo = (int*) allocate((max_ascii + 1) * sizeof(int));
            for(i = 0; i <= max_ascii; i++)
               crivo[i] = 1;
         }
            
         #pragma omp barrier   
         //Executa o algoritmo do crivo de Erastótenes
         erastotenes(&crivo, max_ascii, id, nodes);
         #pragma omp barrier   
            
         //Cria um vetor com todos os primos do intervalo
         if(id == 0)
         {
            for(i = 2, num_primos = 0; i <= max_ascii; i++)
               if(crivo[i])
                  num_primos++;
            primos = allocate(num_primos * sizeof(int));
            for(i = 2, j = 0; j < num_primos; i++)
               if(crivo[i])
                  primos[j++] = i;
         }

         #pragma omp barrier 
         for(i = 0; i < num_palindromos_thread; i++)
            if(busca_binaria(primos, num_primos, soma_ascii[i]))
               printf("(%d, %d): %d\n", id, i + 1, soma_ascii[i]);               
      }         
   }   
   printf("\n");
   
   //Término da contagem de tempo
   gettimeofday(&tf, NULL);
   sec = tf.tv_sec - ti.tv_sec;
   if(tf.tv_usec < ti.tv_usec)
      sec--;
   usec = (tf.tv_usec - ti.tv_usec + 1000000) % 1000000;
   printf("Tempo decorrido: %ld.%06ld s.\n", sec, usec);
   return 0;   
}

//Aloca memoria, finaliza o programa em caso de erro
void* allocate(int bytes)
{
   void *ptr;
   
   ptr = malloc(bytes);
   if(ptr == NULL)
   {
      printf("Erro na alocação de memória.\n");
      exit(0);
   }
   
   return ptr;
}

//Verifica se a palavra é palíndromo 
int palindromo(char* palavra)
{
   int i, len;
   
   len = strlen(palavra);
   
   if(len < 2)
      return 0;
   for(i = 0; i < len/2; i++)
      if(palavra[i] != palavra[len - i - 1])
         return 0;
         
   return 1;
}

//Retorna a soma dos códigos ASCII da palavra
int word_to_ascii(char* palavra)
{
   int i, soma;
   
   soma = 0;
   for(i = 0; palavra[i] != '\0'; i++)
      soma += (int) palavra[i];
   
   return soma;
}

//Algoritmo do crivo de Erastótenes, modificado para execução paralela
void erastotenes(int** crivo, int max_primo, int rank, int nodes)
{
   int i, j, start, end;

   i = (int) sqrt(max_primo) + 1;
   start = rank * (i / nodes);
   end = (rank + 1) * (i / nodes);
   if(rank == 0)
      start = 2;
   if(rank == nodes - 1)
      end = i;

   for(i = start; i < end; i++)
         if((*crivo)[i])
            for(j = 2 * i; j <= max_primo; j += i)
               (*crivo)[j] = 0;

   return;
}

//Busca binária (utilizada na verificação de se um número é primo)
int busca_binaria(int* vetor, int tamanho, int chave)
{
   int idmin, idmax, idmed;
   
   idmin = 0;
   idmax = tamanho - 1;
   
   while(idmin != idmax)
   {
      idmed = (idmin + idmax) / 2;
      
      if(idmed == idmin || idmed == idmax)
         if(vetor[idmin] == chave || vetor[idmax] == chave)
            return 1;
         else
            return 0;
      
      if(chave > vetor[idmed])
         idmin = idmed;
      else if(chave < vetor[idmed])
            idmax = idmed;
           else
            return 1;
   }
   
   return 0;
}
